package tree

import "math"

/**
有效的二叉搜索树
 */


func isValidBST(root *TreeNode) bool {
	return ValidBSTV2(root, math.MaxInt, math.MinInt)
}


func ValidBSTV2(root *TreeNode, max int, min int) bool {
	if root == nil {
		return true
	}

	if root.Val < min || root.Val > max {
		return false
	}

	return ValidBSTV2(root.Left, root.Val, min) && ValidBSTV2(root.Right, max, root.Val)
}


func ValidBST(root *TreeNode, middleVal int, tag string) bool {

	if root == nil {
		return true
	}

	if root.Left != nil {
		if root.Left.Val >= root.Val {
			return false
		}

		if tag != "" {
			if tag == "left" && root.Left.Val >= middleVal {
				return false
			}

			if tag == "right" && root.Left.Val <= middleVal {
				return false
			}
		}
	}

	if root.Right != nil {
		if root.Right.Val <= root.Val {
			return false
		}

		if tag != "" {
			if tag == "left" && root.Right.Val >= middleVal {
				return false
			}

			if tag == "right" && root.Right.Val <= middleVal {
				return false
			}
		}
	}

	var (
		r1 = true
		r2 = true
	)

	if root.Left != nil {
		r1 = ValidBST(root.Left, root.Val, "left")
	}

	if root.Right != nil {
		r2 = ValidBST(root.Right, root.Val, "right")
	}

	return r1 && r2
}



